package main

import (
	"fmt"
	"sort"
)

func largestSumAfterKNegations(nums []int, k int) int {
	sort.Sort(sort.IntSlice(nums))

	var len = len(nums)
	var i = 0
	var lessZeroCount = 0
	for i = 0; i < len-1; i++ {
		if nums[i+1] > 0 {
			break
		} else {
			lessZeroCount++
		}
	}
	if lessZeroCount == 0 {
		if k%2 == 1 {
			nums[0] = 0 - nums[0]
		}
	} else {
		var j = 0
		for j = 0; j < i && k > 0; j++ {
			nums[j] = 0 - nums[j]
			k--
		}
		if j == i && k > 0 {
			if k%2 == 1 {
				nums[j] = 0 - nums[j]
			} else {
				if i+1 < len {
					if 0-nums[j] > nums[i+1] {
						nums[j] = 0 - nums[j]
						nums[i+1] = 0 - nums[i+1]
					}
				}
			}
		}
	}
	var sum = 0
	for _, x := range nums {
		sum += x
	}
	return sum
}

func main() {
	var arr = [9]int{8, -7, -3, -9, 1, 9, -6, -9, 3}
	fmt.Println(largestSumAfterKNegations(arr[:], 8))
	var arr2 = [6]int{-8, 3, -5, -3, -5, -2}
	fmt.Println(largestSumAfterKNegations(arr2[:], 6))
	var arr3 = [5]int{2, -3, -1, 5, -4}
	fmt.Println(largestSumAfterKNegations(arr3[:], 2))
}
